package bbGraphs;
import java.util.*;

public class Graph implements Cloneable
{
	public Map< Integer, Set< Integer > > m_edgeMap;
	public Map< Integer, Node > m_nodeMap;
	public ArrayList< Pair< Integer, Integer > > m_edgeList;
	public Map< Node.COLOR, Set< Integer > > m_coloredNodes;
	
	
	public Graph()
	{
		m_edgeMap = new HashMap< Integer, Set< Integer > >();
		m_nodeMap = new HashMap< Integer, Node >();
		m_edgeList = new ArrayList< Pair< Integer, Integer > >();
		m_coloredNodes = new HashMap< Node.COLOR, Set< Integer > >();
		m_coloredNodes.put( Node.COLOR.RED, new TreeSet< Integer >() );
		m_coloredNodes.put( Node.COLOR.BLUE, new TreeSet< Integer >() );
	}
	
	public void addEdge( Integer _sourceID, Integer _destID )
	{
		// These are 2-way edges, so let's add both ways
		if( ! m_edgeMap.containsKey( _sourceID ) )
		{
			m_edgeMap.put( _sourceID, new HashSet< Integer >() );
		}
		m_edgeMap.get( _sourceID ).add( _destID );
		
		if( ! m_edgeMap.containsKey( _destID ) )
		{
			m_edgeMap.put( _destID, new HashSet< Integer >() );
		}
		m_edgeMap.get( _destID ).add( _sourceID );
		
		// For ease of computation later, we'll create a list of edges.
		// The order of source and destination aren't important as long as
		// there is only one unique edge per Pair
		m_edgeList.add( new Pair< Integer, Integer >( _sourceID, _destID ) );
		
	}
	
	public void addNode( int _ID, Node _node )
	{
		m_nodeMap.put( _ID, _node );
	}
	
	public void setNodeColor( int _ID, Node.COLOR _color )
	{
		m_nodeMap.get( _ID ).color = _color;
		m_coloredNodes.get( _color ).add( _ID );
	}
	
	public Node.COLOR getNodeColor( int _ID )
	{
		return m_nodeMap.get( _ID ).color;
	}
	
	public void resetNodeColor( int _ID )
	{
		m_nodeMap.get( _ID ).color = Node.COLOR.WHITE;
		if( m_coloredNodes.get( Node.COLOR.RED ).contains( _ID ) )
			 m_coloredNodes.get( Node.COLOR.RED ).remove( _ID );
		else
			m_coloredNodes.get( Node.COLOR.BLUE ).remove( _ID );
	}
	
	static public HashMap< Integer, Double > degreeCentralityList( Graph _graph )
	{
		HashMap< Integer, Double > nodeMap = new HashMap< Integer, Double >();
		
		for( int key : _graph.m_edgeMap.keySet() )
		{
			nodeMap.put( key, (double)_graph.m_edgeMap.get( key ).size() );
		}
		return nodeMap;
	}
	
	static public HashMap< Integer, Double > closenessCentralityList( Graph _graph )
	{
		HashMap< Integer, Double > nodeMap = new HashMap< Integer, Double >();
		Integer distances[][] = new Integer[ _graph.m_nodeMap.size() ][ _graph.m_nodeMap.size() ];
		for( int firstIndex = 0; firstIndex < _graph.m_nodeMap.size(); ++firstIndex )
		{
			for( int secondIndex = 0; secondIndex < _graph.m_nodeMap.size(); ++secondIndex )
			{
				if( firstIndex == secondIndex )
				{
					distances[ firstIndex ][ secondIndex ] = 0;
				}
				else
				{
					distances[ firstIndex ][ secondIndex ] = Integer.MAX_VALUE;
				}	
			}
		}
		
		for( int src: _graph.m_edgeMap.keySet() )
		{
			for( int dest: _graph.m_edgeMap.get( src ) )
			{
				distances[ src ][ dest ] = 1;
			}
		}
		
		for( int outerIndex = 0; outerIndex <  _graph.m_nodeMap.size(); ++outerIndex )
		{
			for( int middleIndex = 0; middleIndex <  _graph.m_nodeMap.size(); ++middleIndex )
			{
				for( int innerIndex = 0; innerIndex <  _graph.m_nodeMap.size(); ++innerIndex )
				{
					distances[ middleIndex ][ innerIndex ] = Math.min( distances[ middleIndex ][ innerIndex ], distances[ middleIndex ][ outerIndex ]+ distances[ outerIndex ][ innerIndex ] );
				}
			}
		}
		
		for( int baseNode = 0; baseNode <  _graph.m_nodeMap.size(); ++baseNode )
		{
			int totalDist = 0;
			for( int destNode = 0; destNode <  _graph.m_nodeMap.size(); ++destNode )
			{
				totalDist = totalDist + distances[ baseNode ][ destNode ];
			}
			nodeMap.put( baseNode, ( (double)totalDist / (double)_graph.m_nodeMap.size() ) );
		}
		
		return nodeMap;
	}
	
	static public void initializeActiveEdges( Graph _graph, float _activeEdgeProb )
	{
		Random generator = new Random();
	
		for( int listIndex = _graph.m_edgeList.size() - 1; listIndex >= 0; --listIndex )
		{
			double randNum = generator.nextDouble();
			if( randNum > _activeEdgeProb ) // Shahrzad: if(randNum > _activeEdgeProb)
			{
				_graph.m_edgeList.remove( listIndex );
			}
		}
		
		ArrayList< Pair< Integer, Integer > > _tempEdgeList = new ArrayList< Pair< Integer, Integer > >();
		for( Pair< Integer, Integer > edge: _graph.m_edgeList )
		{
			_tempEdgeList.add( new Pair< Integer, Integer >( edge.getLeft(), edge.getRight() ) );
		}
		
		// Now let's reset the all edges in the graph
		_graph.m_edgeMap.clear();
		_graph.m_edgeList.clear();
		
		for( Pair< Integer, Integer > edge: _tempEdgeList )
		{
			_graph.addEdge( edge.getLeft() , edge.getRight() );
		}
	}
	
	static public HashMap< Integer, HashMap< Integer, Set< Integer > > > getNodeDistances( Graph _graph )
	{
		HashMap< Integer, HashMap< Integer, Set< Integer > > > nodeDistMap = new HashMap< Integer, HashMap< Integer, Set< Integer > > >();
		Integer distances[][] = new Integer[ _graph.m_nodeMap.size() ][ _graph.m_nodeMap.size() ];
		for( int firstIndex = 0; firstIndex < _graph.m_nodeMap.size(); ++firstIndex )
		{
			for( int secondIndex = 0; secondIndex < _graph.m_nodeMap.size(); ++secondIndex )
			{
				if( firstIndex == secondIndex )
				{
					distances[ firstIndex ][ secondIndex ] = 0;
				}
				else
				{
					distances[ firstIndex ][ secondIndex ] = Integer.MAX_VALUE;
				}	
			}
		}
		
		for( int src: _graph.m_edgeMap.keySet() )
		{
			for( int dest: _graph.m_edgeMap.get( src ) )
			{
				distances[ src ][ dest ] = 1;
			}
		}
		
		for( int outerIndex = 0; outerIndex <  _graph.m_nodeMap.size(); ++outerIndex )
		{
			for( int middleIndex = 0; middleIndex <  _graph.m_nodeMap.size(); ++middleIndex )
			{
				for( int innerIndex = 0; innerIndex <  _graph.m_nodeMap.size(); ++innerIndex )
				{
					distances[ middleIndex ][ innerIndex ] = Math.min( distances[ middleIndex ][ innerIndex ], distances[ middleIndex ][ outerIndex ]+ distances[ outerIndex ][ innerIndex ] );
				}
			}
		}
		
		for( int baseNode = 0; baseNode <  _graph.m_nodeMap.size(); ++baseNode )
		{
			HashMap< Integer, Set< Integer > > distMap = new HashMap< Integer, Set< Integer > >();
			for( int destNode = 0; destNode <  _graph.m_nodeMap.size(); ++destNode )
			{
				int distance = distances[ baseNode ][ destNode ];
				if( ! distMap.containsKey( distance ) )
				{
					distMap.put( distance, new TreeSet< Integer >() );
				}
				
				distMap.get( distance ).add( destNode );
				
			}
			nodeDistMap.put( baseNode, distMap );
		}
		
		return nodeDistMap;
	}
	
	// This function only returns the difference between red and blue nodes 
	//Shahrzad: This implements the Distance-based Propagation model
	static public int propagate( Graph _graphInstance )
	{
		// We'll subtract 1 for every red node created, we'll add 1 for every blue node
		int nodeColorDiff = 0;
		
		//Shahrzad: We don't need the random 
		// Random generator = new Random();
		
		// We'll have to get all of the node distances first
		HashMap< Integer, HashMap< Integer, Set< Integer > > > nodeDistances = getNodeDistances( _graphInstance );
		
		for( int nodeID = 0; nodeID < _graphInstance.m_nodeMap.size(); ++nodeID )
		{
			int redInfluence = 0;
			int blueInfluence = 0;
			
			//Shahrzad: What about the initial adopters?
			// I mean the nodes that are already red or Blue? Then we don't need to even look at the other blue or red nodes in its neighborhood
			//We need to count them in the difference between Red and Blue
			
			for( int distance = 1; distance < _graphInstance.m_nodeMap.size() ;++distance )
			{
				// If there's nothing in this set, move on
				if( ! nodeDistances.get( nodeID ).containsKey( distance ) )
					continue;
				
				Iterator< Integer > nodeIter = nodeDistances.get( nodeID ).get( distance ).iterator();
				
				while( nodeIter.hasNext() )
				{
					if( _graphInstance.m_coloredNodes.get( Node.COLOR.RED ).contains( nodeIter.next() ) )
						++redInfluence;
					else if( _graphInstance.m_coloredNodes.get( Node.COLOR.BLUE ).contains( nodeIter.next() ) )
						++blueInfluence;
				}
				
				// If we found any influencing nodes, we'll break and figure out the winner later 
				if( ( redInfluence > 0 ) || ( blueInfluence > 0 ) )
					break;	
			}
			
			if( ( redInfluence > 0 ) || ( blueInfluence > 0 ) )
			{
				if( blueInfluence == 0 )
				{
					--nodeColorDiff;
				}
				else if( redInfluence == 0 )
				{
					++nodeColorDiff;
				}
				else
				{
					//Shahrzad: We just need the probability that the node becomes blue or red, we don't need to specify that it finally becomes red or blue
					nodeColorDiff+= (blueInfluence-redInfluence)/( blueInfluence + redInfluence );
					//if( generator.nextInt( blueInfluence + redInfluence ) < blueInfluence )
					//	++nodeColorDiff;
					//else
					//	--nodeColorDiff;
				}
				
			}
			
		}
		
		return nodeColorDiff;
	}
	
	public Object clone() throws CloneNotSupportedException 
	{
		Graph clone = ( Graph )super.clone();

	    // Deep copy the edgeMap values;
		for( int srcID : this.m_edgeMap.keySet() )
		{
			for( int dstID: this.m_edgeMap.get( srcID ) )
				clone.addEdge( srcID, dstID  );
		}
		
		for( int srcID : this.m_nodeMap.keySet() )
		{
			clone.addNode( srcID, new Node( srcID ) );
		}
		
	    return clone;	
	}
}

